package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月22日
*时间：上午9:59:28
*/
public class Q135 {
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    List<List<Integer>> rs = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length <= 0) {
            return rs;
        }
        List<Integer> result = new ArrayList<>();
        Arrays.sort(candidates);
        for (int i = 0; i < candidates.length; i++) {
            if (!result.contains(candidates[i])) {
                result.add(candidates[i]);
            }
        }
        int copy[] = new int[result.size()];
        int count = 0;
        for (int i : result) {
            copy[count++] = i;
        }
        result.clear();
        combinationSum(copy, target, 0, 0, result);
        return rs;
    }

    private void combinationSum(int[] candidates, int target, int index, int sum, List<Integer> result) {
        List<Integer> l = new ArrayList<>(result);
        if (sum > target) {
            return;
        } else if (sum == target) {
            rs.add(l);
        } else {
            for (int i = index; i < candidates.length; i++) {
                l.add(candidates[i]);
                sum += candidates[i];
                combinationSum(candidates, target, i, sum, l);
                sum -= candidates[i];
                l.remove((Integer) candidates[i]);
            }
        }
    }

    @Test
    public void testA() {
        int[] candidates = { 8, 7, 4, 3 };
        int target = 11;
        System.out.println(combinationSum(candidates, target));
    }
}
